// https://www.lintcode.com/problem/kth-largest-in-n-arrays/description

// class Solution {
// public:
    /**
     * @param arrays: a list of array
     * @param k: An integer
     * @return: an integer, K-th largest element in N arrays
     */
     
    // O(NMlogk) 不适合k大的时候 遍历所有，堆大小为k
    // int KthInArrays(vector<vector<int>> &arrays, int k) {
    //     priority_queue<int, vector<int>, greater<int>> q;
    //     for (int i = 0; i < arrays.size(); ++i)
    //     {
    //         for (int j = 0; j < arrays[i].size(); ++j)
    //         {
    //             if (q.size() == k)
    //             {
    //                 if (arrays[i][j] > q.top())
    //                 {
    //                     q.pop();
    //                     q.push(arrays[i][j]);
    //                 }
    //             }
    //             else
    //             {
    //                 q.push(arrays[i][j]);
    //             }
    //         }
    //     }
    //     return q.top();
    // }
// };


// O(NMlogM+klogN) k次，堆大小N.适合m小的时候
// 直到第k个？为什么能确保这个队列中的下一个比其他队列中的小。
// 因为替换了之后个数还和原来一样啊。堆大小不变，操作k次得到的就是第k小。
// 好像不用担心队列为空，每组最后一个数都记了，都可以往前取的
class Node {
    public:
        int x;
        int y;
        int val;
        Node (int x, int y, int val)
        {
            this->x = x;
            this->y = y;
            this->val = val;
        }
        // 运算符重载 https://www.runoob.com/cplusplus/cpp-overloading.html
        bool operator < (const Node & obj) const //最后一个const不加报错
        {
            return this->val < obj.val;
        }
};
class Solution {
public:
    int KthInArrays(vector<vector<int>> &arrays, int k) {
        priority_queue<Node> q;
        int n = arrays.size();
        for (int i = 0; i < n; ++i)
        {
            sort(arrays[i].begin(), arrays[i].end());
            int m = arrays[i].size();
            if (m > 0) //注意，有空的
                q.push(Node(i, m - 1, arrays[i][m - 1]));
        }
        for (int i = 0; i < k - 1; ++i)
        {
            Node tmp = q.top();
            cout << tmp.val << endl;
            q.pop();
            if (tmp.y > 0)
            {
                q.push(Node(tmp.x, tmp.y - 1, arrays[tmp.x][tmp.y - 1]));
            }
        }
        return q.top().val;
    }
};